# 深度优先 案例
# 二叉树的最大深度
"""
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。
"""


# definition for a binary tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        if root.left == None and root.right == None:
            return 1
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1


"""给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
 /   \
2     3
 \
  5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
"""


# 递归查找
class Solution1:
    def binaryTreePaths(self, root: TreeNode) -> list[str]:
        if not root:
            return []
        if not root.left and not root.right:
            return [str(root.val)]
        path_list = []
        if root.left:
            path_list += self.binaryTreePaths(root.left)
        if root.right:
            path_list = self.binaryTreePaths(root.right)
        for index, path in enumerate(path_list):
            path_list[index] = str(root.val) + "->" + path
        return path_list


# 迭代查询
class Solution2:
    def binaryTreePaths(self, root: TreeNode) -> list[str]:
        if not root:
            return []
        path_list, stack = [], [(root, "")]
        while stack:
            node, path_str = stack.pop(0)
            if not node.left and not node.right:
                path_list.append(path_str + str(node.val))
            if node.left:
                stack.append((node.left, path_str + str(node.val) + "->"))
            if node.right:
                stack.append((node.right, path_str + str(node.val) + "->"))
        return path_list


"""给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 
给定如下二叉树，以及目标和 sum = 22，
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。"""


class Solution3:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False
        if sum == root.val and root.left is None and root.right is None:
            return True
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(
            root.right, sum - root.val
        )
